package LeetCode.BitCompute;

/**
 * 判断一个数是不是 4 的 n 次方
 * <p>
 * 342. 4的幂
 * https://leetcode-cn.com/problems/power-of-four/
 * 给定一个整数 (32 位有符号整数)，请编写一个函数来判断它是否是 4 的幂次方。
 * <p>
 * 示例 1:
 * <p>
 * 输入: 16
 * 输出: true
 * 示例 2:
 * <p>
 * 输入: 5
 * 输出: false
 * 进阶：
 * 你能不使用循环或者递归来完成本题吗？
 * ==================
 * 思路
 * 这种数在二进制表示中有且只有一个奇数位为 1，例如 16（10000）。
 */
public class Test8 {
    public static boolean isPowerOfFour(int num) {

        //0x55555555在32位系统里表示0b01010101010101010101010101010101。
        //十六进制数：0x55555555 5即0101 int为32位 二进制即：0b01010101010101010101010101010101

        //4的幂特点：在二进制表示中有且只有一个奇数位为 1
        //1. num > 0 正数
        //2. (num & (num-1)) == 0 保证只有一个1
        //3. (num  & 0x55555555) != 0 保证1在奇数位

        //return ((num & (num-1)) == 0) && num > 0 && ((num  & 0x55555555) != 0)
//        return num > 0 && (num & (num - 1)) == 0 && (num & 0b01010101010101010101010101010101) != 0;
        //法二：正则表达式
//        return Integer.toString(num, 4).matches("10*");
        //法三：常规解法
        if (num == 1) return true;
        while (num % 4 == 0)//除4取余为0 (若可被4整除则继续)
        {
            num = num / 4;//除4取整
            System.out.println(num);
            if (num == 1) return true;//为1则说明为4的幂
        }
        return false;


    }

    public static void main(String[] args) {
        System.out.println(isPowerOfFour(16));
    }
}
